The present invention relates to cyclic redundancy calculation circuitry. More particularly, the present invention pertains to generator polynomials for use in cyclic redundancy calculations, such as, for example, those performed for use in error detection in implantable medical devices.
Various devices use cyclic redundancy checking for error detection. For example, as described in U.S. Pat. No. 5,354,319 to Wyborny et al., issued Oct. 11, 1994 and entitled xe2x80x9cTelemetry System for an Implantable Medical Device,xe2x80x9d cyclic redundancy checking is used for link error detection in the communication of information between an implantable device to an external receiver. Further, other types of transmission and/or storage devices use cyclic redundancy checking for error detection purposes. For example, digital cellular systems transmitting digitized speech data utilize cyclic redundancy checking.
Generally, cyclic redundancy checking techniques must be customized to operate on the type of errors which are expected to be encountered in a particular system design. Inappropriate choice of coding leads to poor error detection, poor correction, and overuse of system resources.
Generally, to perform cyclic redundancy check encoding or decoding for a block of data, a cyclic redundancy check code, i.e., a remainder polynomial, is calculated by system circuitry. To calculate a cyclic redundancy check code, the data to be encoded or decoded is considered as a long polynomial with binary coefficients. The data polynomial is divided by a generator polynomial, g(x), which has been designed for a desired cyclic redundancy checking performance. Only a small number of polynomials are suitable for use as generator polynomials and generally, a smaller number of such generator polynomials exhibit the proper coding performance for a particular system design.
The calculation of cyclic redundancy checking codes is commonly supported with specialized circuitry designed to generate check bits for a particular generator polynomial. For example, communication control integrated circuits and microprocessor serial ports often incorporate cyclic redundancy checking calculation hardware to generate a particular standard check bit format. For example, U.S. Pat. No. 5,354,319 to Wyborny et al. describes the design of a 16-bit cyclic redundancy check code generating hardware design.
Calculation of multiple formats, for example, calculation of both the common CRC-16 and CCITT-16 polynomials, requires significant duplication of functions and circuitry. Further, generating multiple codes of different length also generally requires duplication of functions and circuitry. For example, generation of a cyclic redundancy check code that is 8-bits long versus a code that is 16-bits long conventionally has required significant duplication of functions and circuitry.
Attempts have been made at providing cyclic redundancy checking which is capable of operating with use of multiple generator polynomials. For example, U.S. Pat. No. 3,678,469 to Freeman et al., issued Jul. 18, 1972 and entitled xe2x80x9cUniversal Cyclic Division Circuit,xe2x80x9d describes a universal cyclic redundancy check generator which stores information about the character size in use and the polynomial to be used for checking data. The stored information is used to control a universal matrix which uses the stored polynomial to generate a cyclic redundancy check code for new data received and combines it with a cumulative cyclic redundancy check character developed by the matrix for previous characters. However, such cyclic redundancy checking designs have generally not taken into consideration the space limitations and low power requirements of low power devices, such as implantable medical devices.
Implantable medical devices are generally designed in view of space limitations and low power requirements. As indicated above, generally, to calculate multiple format cyclic redundancy checking codes, e.g., 8-bit codes and 16-bit codes, in the same system, requires significant duplication of functions and circuitry. Such duplication of functions and circuitry is undesirable, particularly in such low power and space limited applications, e.g., implantable medical devices.
As those of ordinary skill in the art will appreciate readily upon reading the Summary of the Invention, Detailed Description of the Embodiments, and claims set forth below, at least some of the devices and methods disclosed in the references cited herein may benefit advantageously by using the teachings of the present invention. However, listing of any such references in Table 1, or elsewhere herein, is by no means an indication that such references are prior art to the present invention.
The present invention has certain objects. That is, various embodiments of the present invention provide solutions to one or more problems existing in the prior art with respect to use of cyclic redundancy checking techniques. One of such problems involves the lack of methods and devices for efficiently and effectively calculating cyclic redundancy codes of multiple bit lengths, e.g., such as with use of multiple generator polynomials in polynomial division calculations. Further, for example, other problems include the significant duplication of functions and circuitry to provide calculation of such cyclic redundancy codes, the higher power demands of systems which do not include the flexibility of utilizing cyclic redundancy codes of multiple lengths, e.g., 8-bit codes and 16-bit codes, and the inability to lower the power consumption of such systems.
In comparison to known techniques for providing cyclic redundancy checking, various embodiments of the present invention may provide one or more of the following advantages. For example, sharing of generator polynomial terms when implementing cyclic redundancy checking provides for reduced duplication of circuitry and functionality, e.g., minimal hardware usage to provide cyclic redundancy checking. By providing cyclic redundancy codes using multiple generator polynomials, lower power requirements can also be satisfied.
Some embodiments of the present invention include one or more of the following features: the provision of one or more circuits which implement at least a first and second cyclic redundancy code generator polynomial; implementation of a first cyclic redundancy code generator polynomial which is expressed as a first set of terms and a second cyclic redundancy code generator polynomial which is expressed as a second set of terms, wherein the first code generator polynomial is of a higher order than the second code generator polynomial and contains all of the second set of terms of the second cyclic redundancy code generator polynomial; selection between use of a first and second cyclic redundancy code generator polynomial to perform polynomial division for a data stream resulting in a cyclic redundancy code; implementation of a first and second cyclic redundancy code generator polynomial using a first linear feedback shift register circuit and a second linear feedback shift register circuit; implementation of a first and second linear feedback shift register circuit using latches and XOR gates; providing for selection of a first cyclic redundancy code generator polynomial that results in a 16-bit cyclic redundancy code and a code generator polynomial that results in an 8-bit cyclic redundancy code; performing cyclic redundancy polynomial division on a data stream that includes memory data, e.g., data in a non-volatile memory device, or data communicated between a transmitter and a receiver; performing cyclic redundancy calculations within an implantable medical device; a cyclic redundancy code generator apparatus including one or more circuits operable on one or more data blocks to perform a polynomial division using one of at least a first cyclic redundancy code generator polynomial and a second cyclic redundancy code generator polynomial to generate a cyclic redundancy code; and a cyclic redundancy code generator apparatus including a first linear feedback shift register circuit for receiving data and a second linear feedback shift register circuit serially connected to the first linear feedback shift register circuit, wherein such circuits are configured for providing polynomial division on data using a first cyclic redundancy code generator polynomial and also configured for performing the polynomial division on data using a second cyclic redundancy code generator polynomial.
The above summary of the present invention is not intended to describe each embodiment or every implementation of the present invention. Advantages, together with a more complete understanding of the invention, will become apparent and appreciated by referring to the following detailed description and claims taken in conjunction with the accompanying drawings.